main(n,m,i,c,b,w){for(gets(&n);~scanf("%d%d",&n,&m);printf("%d\n",c+(n==2)))for(c=0,i=n+!(n&1);i<=m;c+=!b,i+=2)for(w=3,b=0;w<=i/2;b|=i%w?0:1,w+=2);}
